package com.sunny.l64;

/**
 * @Author zsunny
 * @Date 2018/9/19 15:54
 * @Mail zsunny@yeah.net
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        char[][] matrix = {{'0','0','0'},{'0','0','0'},{'1','1','1'}};
        System.out.println(solution.maximalRectangle(matrix));
    }

    public int maximalRectangle(char[][] matrix) {
        if(null == matrix){
            return 0;
        }
        int n = matrix.length;
        if(0 == n){
            return 0;
        }
        int m = matrix[0].length;
        int[][] arr = new int[n][m];
        int maxRes = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(0 == i){
                    if('1' == matrix[i][j]){
                        arr[i][j] = 1;
                    }else{
                        arr[i][j] = 0;
                    }
                }else{
                    if('1' == matrix[i][j]){
                        arr[i][j] = arr[i-1][j]+1;
                    }else{
                        arr[i][j] = 0;
                    }
                }
            }
            int tmpRes = getRes(arr[i]);
            if(maxRes < tmpRes){
                maxRes = tmpRes;
            }
        }
        return maxRes;
    }

    public int getRes(int[] arr){
        int res = 0;
        int len = arr.length;
        int[] left = new int[len];
        int[] right = new int[len];
        left[0] = 0;
        for(int i=1;i<len;i++){
            int ind = i;
            while (ind > 0 && arr[i] <= arr[ind-1]){
                ind = left[ind-1];
            }
            left[i] = ind;
        }
        right[len-1] = len-1;
        for(int i=len-2;i>=0;i--){
            int ind = i;
            while (ind < len-1 && arr[i] <= arr[ind+1]){
                ind = right[ind+1];
            }
            right[i] = ind;
        }
        for(int i=0;i<len;i++){
            int tmpRes = arr[i]*(right[i]-left[i]+1);
            if(tmpRes > res){
                res = tmpRes;
            }
        }
        return res;
    }
}